In a typical wireless network where a coordination function is utilized for coordinating transmissions among wireless stations, such a coordination function may be implemented in one of the wireless stations or an access point (coordinator). The wireless stations may be consumer electronics (CE) devices which communicate via directional transmissions using sector antennas and beam forming antenna arrays. The coordinator may use omni-directional transmissions (e.g., 360 degrees range) to broadcast to all stations in all directions. Or the coordinator may use quasi-omni-directional transmissions to broadcast to a wide range, but not necessarily 360 degrees. However, when directional transmission is used by two stations to transmit to a coordinator, the two stations may interfere with directional transmissions of each other but cannot hear each other. This prevents carrier sensing for the two stations when attempting random access to a wireless communication medium for communication. When transmissions are directional, preamble sensing is not available. Also the number of transmission opportunities is fixed. This lowers the random access efficiency as well.